﻿// 0729train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <limits.h>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>

using namespace std;

/*
石头、剪刀、布，字母 A , B , C

 A > B；B > C；C > A；">"左边一个字母，表示相对优势形状。
 右边一个字母，表示相对劣势形状。
 当本场次中有且仅有一种出拳形状优于其它出拳形状，则该形状的玩家是胜利者。
 否则认为是平局。
 当发生平局，没有赢家。有多个胜利者时，同为赢家。

例如 1： 三个玩家出拳分别是A, B, C ，由于出现三方优势循环(即没有任何一方优于其它出拳者)，判断为平局。
例如 2： 三个玩家，出拳分别是 A, B ，出拳 A 的获胜。
例如 3： 三个玩家，出拳全部是 A ，判为平局。


输入描述
在一场游戏中，每个玩家的信息为一行。玩家数量不超过 1000 。每个玩家信息有 2 个字段，用空格隔开：
1. 玩家 ID：一个仅由英文字母和数字组成的字符串
2. 出拳形状：以英文大写字母表示, A 、B 、C 形状。
例：
abc1 A
xyz B

输出
输出为赢家的玩家 ID 列表(一个或多个)，每个 ID 一行，按字符串升序排列。
如果没有赢家，输出为"NULL"字符串。
例如：
abc1


输入
abc1 A
xyz A
输出
NULL

 */

void GetPlayerVec(vector<string>&player_info_vec, vector<vector<string>>&result_vec)
{
	vector<string>player_vec;
	vector<string>char_vec;
	for (int i=0; i<player_info_vec.size();i++)
	{
		string str_1 = player_info_vec[i];
		stringstream sstream_1(str_1);
		string token;
		int count = 0;
		vector<string>tmp_str_vec(2);

		while (sstream_1 >> token && count < 2)
		{
			tmp_str_vec[count] = token;
			count++;
		}
		player_vec.push_back(tmp_str_vec[0]);
		char_vec.push_back(tmp_str_vec[1]);

	}

	result_vec[0] = player_vec;
	result_vec[1] = char_vec;
	
	//GetPlayerVec
}



void solve01(vector<string>player_info_vec)
{

	unordered_set<char>oh_set;
	vector<vector<string>>origin_vec(2);
	GetPlayerVec(player_info_vec, origin_vec);
	vector<string>player_vec = origin_vec[0];
	vector<string>char_vec = origin_vec[1];
	
	for (auto &char_str:char_vec)
	{
		char oh_char = char_str[0];
		if (!oh_set.count(oh_char))
		{
			oh_set.insert(oh_char);
		}
	}
	if (oh_set.size()==3 || oh_set.size() == 1)
	{
		cout << "NULL";
		return;
	}

	//A > B；B > C；C > A
	char win_char;
	if (oh_set.count('A')&& oh_set.count('B'))
	{
		win_char = 'A';
	}
	else if (oh_set.count('B') && oh_set.count('C'))
	{
		win_char = 'B';
	}
	else if (oh_set.count('C') && oh_set.count('A'))
	{
		win_char = 'C';
	}

	vector<string>result_vec;
	for (int i=0; i<char_vec.size();i++)
	{
		string char_str = char_vec[i];
		char oh_char = char_str[0];
		if (oh_char==win_char)
		{
			result_vec.push_back(player_vec[i]);
		}
	}
	//比较字符串，不需要写Compare!
	sort(result_vec.begin(), result_vec.end());

	for (auto&str:result_vec)
	{
		cout << str << endl;
	}
	//solve01
	//------
}


/*
题目
主管期望你来实现英文输入法单词联想功能，需求如下：
1. 依据用户输入的单词前缀，从已输入的英文语句中联想出用户想输入的单词。
2. 按字典序输出联想到的单词序列，如果联想不到，请输出用户输入的单词前缀。
注意：
1. 英文单词联想时区分大小写
2. 缩略形式如"don't" 判定为两个单词"don"和 "t"
3. 输出的单词序列不能有重复单词，且只能是英文单词，不能有标点符号
输入
输入两行。
首行输入一段由英文单词word和标点构成的语句str，接下来一行为一个英文单词前缀pre。
0 < word.length() <= 20，
0 < str.length() <= 10000，
0 < pre.length() <= 20
输出
输出符合要求的单词序列或单词前缀。存在多个时，单词之间以单个空格分割

输入
I love you
He

输出
He


输入
The furthest distance in the world,Is not between life and death,But when I stand in front or you,Yet you don't know that I love you.
f
输出
front furthest


输入
front furthest furthest
f

输入
bub bksbd ahoihd aih lkhfh,lkj dhrn lkdaf bgoh
b
输出
bgoh bksbd bub

 */

bool IsCharVerify(char oh_char)
{
	bool result = false;
	if (oh_char >= 'A' && oh_char <= 'Z')
	{
		result = true;
	}
	else if (oh_char >= 'a' && oh_char <= 'z')
	{
		result = true;
	}
	return result;
}

bool IsMatch(string oh_str, string target_str)
{
	bool result = true;

	for (int i=0; i<target_str.size();i++)
	{
		if (oh_str[i]!=target_str[i])
		{
			result = false;
		}
	}

	return result;

	//IsMatch
	//------
}


void solve02(vector<string>oh_vec, string target_str)
{
	vector<string>str_vec;
	unordered_set<string>oh_set;

	for (int i=0; i<oh_vec.size();i++)
	{
		string curr_str = oh_vec[i];
		bool is_match = IsMatch(curr_str, target_str);

		if (is_match && !oh_set.count(curr_str))
		{
			oh_set.insert(curr_str);
			str_vec.push_back(curr_str);
		}

	}

	if (str_vec.empty())
	{
		cout << target_str;
		return;
	}

	sort(str_vec.begin(), str_vec.end());

	int str_vec_size = str_vec.size();
	for (int i=0; i< str_vec_size; i++)
	{
		if (i!= str_vec_size -1)
		{
			cout << str_vec[i] << ' ';
		}
		else
		{
			cout << str_vec[i];
		}
	}


	//solve02
	//------
}


/*
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，
j > i 且 prices[j] <= prices[i] 的 最小下标 ，
如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。

 */

void solve03(vector<int>&prices)
{
	//prices = [8,4,6,2,3]
	//[4,2,4,2,3]
	vector<int>result;
	vector<int>oh_vec = prices;
	for (int i=0; i< oh_vec.size();i++)
	{
		int curr_num = oh_vec[i];
		bool is_verify = false;
		for (int j=i+1; j< oh_vec.size(); j++)
		{
			int next_num = oh_vec[j];
			if (next_num<=curr_num)
			{
				result.push_back(curr_num - next_num);
				is_verify = true;
				break;
			}
		}
		if (!is_verify) result.push_back(curr_num);
	}

	for (auto&item:result)
	{
		cout << item << ' ';
	}
	
	//solve03
	//------
}


void solve031(vector<int>&prices)
{
	stack<int>oh_stack;
	vector<int>oh_vec = prices;
	int oh_vec_size = oh_vec.size();

	vector<int>result_vec(oh_vec_size);
	for (int i = oh_vec_size-1; i>=0; i--)
	{
		int curr_num = oh_vec[i];
		while (!oh_stack.empty()&&oh_stack.top()> curr_num)
		{
			oh_stack.pop();
		}

		if (!oh_stack.empty())
		{
			result_vec[i] = curr_num - oh_stack.top();
		}
		else
		{
			result_vec[i] = curr_num;
		}
		oh_stack.push(curr_num);
		//------for
	}

	for (auto &item: result_vec)
	{
		cout << item << ' ';
	}
	
	//solve031
	//------
}


int main()
{
	{
		vector<int>prices = { 8,4,6,2,3 };
		solve031(prices);
		return 0;
	}


	//{
	//	//bgoh b
	//	cout << IsMatch("bgoh", "b");
	//	return 0;
	//}

	{
		string input;
		getline(cin, input);

		input = input + " ";
		vector<string>str_vec;
		string curr_str;
		for (int i=0; i<input.size();i++)
		{
			char curr_char = input[i];
			if (IsCharVerify(curr_char))
			{
				curr_str += curr_char;
			}
			else
			{
				if (!curr_str.empty())
				{
					str_vec.push_back(curr_str);
					curr_str = "";
				}
			}
		}
		string target;
		getline(cin, target);

		for (auto &item:str_vec)
		{
			cout << item << endl;
		}
		//string oh_str = "life";
		//string target_str = "f";
		
		//cout << IsMatch(oh_str, target_str);
		//vector<string>str_vec = { "front","furthest" };
		//string target = "f";
		solve02(str_vec, target);

		return 0;
	}


	string input;
	vector<string>player_info_vec;

	while (getline(cin, input) && !input.empty())
	{
		player_info_vec.push_back(input);
	}
	cout << player_info_vec.size();

	
	//vector<string>player_info_vec = {"xyz B", "AZMbKIqNmc A","AbDqE A" };
	solve01(player_info_vec);

	

	//main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
